#include <iostream>
#include <cassert>
#include <vector>
#include <algorithm>
#include <sstream>
#include <list>
#include <stack>
#include <queue>
#include <map>
using namespace std;

struct ListNode {
     int val;
     ListNode *next;
     ListNode() : val(0), next(nullptr) {}
     ListNode(int x) : val(x), next(nullptr) {}
     ListNode(int x, ListNode *next) : val(x), next(next) {}
};
//打印链表
void displayList(ListNode *p){
    while( p ){
        cout<< p->val ;
        p = p->next;
        if(p) cout<<"->";
    }
    cout<<endl;
}


void Binarycout(uint32_t n) 
{ 
    for (int i=31;i>=0;i--) 
    { 
        cout<<((n>>i)&1); 
    } 
    cout<<endl; 
} 
//解决方案类
class Solution {
public:
    int mySqrt(int x) {
        int left=1,right=x/2;
        while(1){
            if(left*left == x)return left;
            else if(right*right == x )return right;
            else {
                if( x/left > left) left++;
                if(x/right < right) right=x/right;
                if(left*left - x > 0 && right*right - x<0)break;
            }
        }
        return right;
    }
};
int main(){
    Solution sp;
    cout<<sp.mySqrt(15)<<endl;
    return 0;
}